HW#1 --- last modified January 29 2019 18:55:49..

Solution set.

Due date: Feb 12

Files to be submitted:
  Hw1.zip

Purpose: To gain experience with probabilistic analysis and our first randomized algorithms.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

LO1 -- Analyze or code a randomized algorithm.

Specification:

This homework will consist of two parts, a written part and a coding part. Both parts will be submitted in the Hw1.zip file. The written part should be in a file Hw1.pdf. For this part of the homework you should write solutions for the following questions. In what you turn in, first copy and paste the question, then write your solution to it beneath it.

1. Suppose we have access to a C function with prototype:

   bool p_random();
   

   which returns 1 with probability `p` and 0 with probability `1-p`. Write a C function

   int dice_random();
   

   which is allowed to call the function p_random that returns a number between `1` to `6` at random each with equal likelihood. dice_random should be your only source of randomness in your code.
2. Consider the variation of the Hiring problem where we have two employees rather than one. As we interview candidates, if we find a candidate that is better than either of our two current employees, we fire the weaker of the current employees and hire the candidate. Determine how many candidates we would hire on average in this situation.
3. Suppose we toss balls into one of n bins. Assume each bin is equally likely. Calculate with work the expected number of balls you would need to toss until there are two bins with at least two balls.

For the coding portion of this assignment I want you to write a simulator for the following computers on a network problem: Imagine you have `n` computers on a network each of which wants to be known by a unique integer ID. The individual computers don't know the value of `n` and the computers are not allowed to openly communicate with each other until they all have a unique identifier. Until that that time they communicate in a restricted way in rounds. In a given round each computer declares a choice of ID. Once all computers have declared their choice, a referee announces whether there were any conflicts. The referee does not say which IDs are in conflict. If there was a conflict, a new round is started; otherwise, the process terminates and everyone uses the ID they chose for subsequent communication. To solve this problem you need to develop and code a protocol each simulated computer runs for choosing IDs. This protocol should compute IDs of at most `O(\log n)` many bits and its correctness should be based on the analysis of priorities in conflict given as part of our in-class proof of correctness for Permute-By-Sorting.

To be a little more specific on what you need to code:

1. Your program should have driver class UIDNetworkDriver. I will test your program by compiling it a command prompt using (I will not install any IDE or build software):

   javac UIDNetworkDriver.java
   

   I will then type the following kind of line at a command prompt on my Mac running Java SE 9 in the folder of your homework:

   java UIDNetworkDriver n mode
   

   Here `n` is an integer representing the number of machines, and `mode` is either verbose or silent. As a concrete example, I might try running your program with:

   java UIDNetworkDriver 5 verbose
   

2. Your program when run with the given parameters, then creates `n` instances of the class MockComputer using the constructor MockComputer().
3. The MockComputer class should have no static variables and only two methods besides the constructor: int round(int i), which computes a new id given that the round number is `i`, and int getId(), which returns the current id the MockComputer is using.
4. After creating the MockComputer instances, your program should then enter into while loop that will cycle through rounds. In a given, round it should call the round(i) method for each MockComputer computer instance. If the mode is verbose, it should output using System.out.print the current round #, followed by the IDs returned by a call to getID() for each MockComputer, followed by max number of bits needed to output any of these IDs. For example, a possible output line might look like:

   Round 2: 4 3 7 3 1 Max Bits 3
   

   Here the biggest number 7 requires 3 bits to write.
5. Your program should output a sequence of such lines until all the IDs are distinct and then stop. In silent mode, your program only needs to output the last line.
6. To convince me your program produces IDs that are `O(\log n)` many bits, I want you to test your program for different values of `n` and produce a plot of `n` versus Max Bits and fit a logarithmic line through the points. Include this graph as part of Hw1.pdf

That completes the description of your program. If you want to use python rather than Java, I will test your program using a version of python 2.7.*. You should name your program UIDNetworkDriver.py and otherwise use same names for classes as I used above.

Point Breakdown